The present invention relates generally to puncture patterns for forward error correcting codes and, more particularly, to a method of puncturing and de-puncturing convolutional codes using a compressed differential puncturing pattern.
The ultimate purpose of a digital communication system is to transmit information from an information source to a destination over a communication channel. In many types of communication channels, such as radio channels, the inherent noise causes bit errors to occur during transmission. In order to reduce bit errors, digital communication systems typically employ both error detecting and error correcting codes. These error control codes introduce controlled redundancy into the information transmitted over the communication channel, which can be used at the destination to detect and/or correct errors in the received signal.
Convolutional codes are one type of forward error correcting codes used in digital communication systems. The code rate k/n of a convolutional code indicates the number of output bits n produced by the encoder for each k input bits. In general, the complexity of the encoder and decoder increases as the number of input bits k increases. Consequently, convolutional encoders with code rates 1/n are desirable from a complexity point of view. However, if k is constrained to “1,” the highest code rate that can be obtained is 1/2.
Puncturing is a technique of constructing new higher rate convolutional codes from an original lower rate convolutional code. For a given low rate convolutional code, it is possible to obtain a plurality of higher rate codes by selectively puncturing coded bits output from the encoder. The punctured bits are not transmitted. The higher rate convolutional codes created by puncturing can be decoded using essentially the same trellis as the original code from which the punctured code is derived. Further, a single encoder/decoder can be used to provide a range of code rates so that the code rate use can be varied, depending upon channel conditions and other factors.
To implement puncturing, a puncture pattern is stored in memory and used to puncture coded bits output by the encoder. One technique used in the prior art is to store an index for each bit to be transmitted. The index is a numerical value that identifies the bit position for each transmitted bit. Depending upon the length of the codeword to be transmitted, this technique requires a very significant amount of storage for the puncturing patterns. For example, an adaptive full rate 8-PSK wideband speech frame contains 1,467 bits after coding but before puncturing. According to the GSM specifications, 1,344 bits of the original 1,467 coded bits are transmitted. Storing a 16-bit index for each transmitted bit would require storage of 21,504 bits.
Another technique for storing puncturing patterns is to store a bit map containing 1 bit for each coded bit output from the encoder. Each bit in the bit map corresponds to a single coded output bit. A bit value of “0” in the bit map indicates that the corresponding bit output by the encoder is punctured, while a bit value of “1” indicates that the corresponding bit is to be transmitted, or vice versa. While this technique reduces the memory requirements for storing puncturing patterns, the processor must compare every coded bit output by the encoder with the bit map to see whether the bit is to be transmitted or punctured. The code needed to perform these comparisons consumes processor cycles increasing the demand on the signal processor. Because some cellular communication systems may use more than 100 logical channels with different puncturing patterns, there is a need for techniques that further reduce the memory requirements for storing the puncturing patterns and that reduce of processor cycles needed for carrying out puncturing/depuncturing operations.